public class Solution304 {
    int[][] markMatrix;
    public Solution304(int[][] matrix) {
        int m=matrix.length;
        int n=m>0? matrix[0].length:0;
        markMatrix=new int[m][n];
        for (int i = 0; i < matrix.length; i++) {
            int[] tmpArr=matrix[i];
            int sum=0;
            for (int j = 0; j < tmpArr.length; j++) {
                sum+=tmpArr[j];
                markMatrix[i][j]=sum;
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int result=0;
        for (int i = row1; i <=row2 ; i++) {
            int beg=col1==0? 0:markMatrix[i][col1-1];
            int end=markMatrix[i][col2];
            result+=end-beg;
        }
        return result;
    }
}
